import java.util.Arrays;

/**
 * @version Create on 2012-10-29
 * @author Yinzi Chen
 */

public class ThreeSumClosest {

	public int threeSumClosest(int[] num, int target) {
		Arrays.sort(num);
		int n = num.length;
		int value = 1000000000;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				int l = j + 1, r = n - 1, mid;
				while (l <= r) {
					mid = l + r >> 1;
					if (num[mid] >= target - num[i] - num[j])
						r = mid - 1;
					else
						l = mid + 1;
				}
				if (r != n - 1) {
					value = Math.abs(value - target) > Math.abs(num[r + 1]
							+ num[i] + num[j] - target) ? num[r + 1] + num[i]
							+ num[j] : value;
				}
				if (value == target)
					break;
				l = j + 1;
				r = n - 1;
				while (l <= r) {
					mid = l + r >> 1;
					if (num[mid] <= target - num[i] - num[j])
						l = mid + 1;
					else
						r = mid - 1;
				}
				if (l != j + 1) {
					value = Math.abs(value - target) > Math.abs(num[l - 1]
							+ num[i] + num[j] - target) ? num[l - 1] + num[i]
							+ num[j] : value;
				}
				if (value == target)
					break;
				while (j + 1 < n && num[j + 1] == num[j])
					j++;
			}
			if (value == target)
				break;
			while (i + 1 < n && num[i + 1] == num[i])
				i++;
		}
		return value;
	}

	public static void main(String[] args) {
		ThreeSumClosest a = new ThreeSumClosest();
		a.threeSumClosest(new int[] { 1, 1, 5, 4, 2 }, 10);
	}

}
